⟸ pàgina anterior ⟸
Exercici 9 (Tasca 2).
(regular languages, NFAs vs DFAs, pigeonhole principle, minimization of DFAs)

Els NFAs poden ser exponencialment més succints que els DFAs

Donat un n\in \mathbb N, considereu el llenguatge L_n = \{ xay \mid x,y \in \{a,b\}^* \land |y| = n\}.

  1. Quin és el cost de l’algorisme de determinització (en funció de la mida de l’NFA d’entrada)?

  2. Demostreu que L_n és regular construïnt un NFA que reconeix L_n amb n+2 estats.

  3. Demostreu que el DFA mínim que reconeix L_n té 2^{n+1} estats. És a dir,

    1. demostreu que existeix un DFA que reconeix L_n amb 2^{n+1} states i
    2. demostreu que cap DFA amb menys de 2^{n+1} estats pot reconèixer L_n.

Recordeu que la notació compacta usada en la definició de L_n correspon al llenguatge \{ w \in \{a,b\}^* \mid \exists x,y\ (w=xay \land |y| = n)\}.